GATE CSE 1996
Q1.
A micro program control unit is required to generate a total of 25 control signals. Assume that during any micro instruction, at most two control signals are active. Minimum number of bits required in the control word to generate the required control signals will be:Q3.
The average number of key comparisons required for a successful search for sequential search on n items isQ4.
A binary search tree is generated by inserting in order the following integers: 50,15,62,5,20,58,91,3,8,37,60,24 The number of nodes in the left subtree and right subtree of the root respectively isQ5.
In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node g?Q7.
Which of the following sequences denotes the post order traversal sequence of the below tree?Q8.
If L_1 and L_2 are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?Q9.
Define a context free languages L \in \{0, 1\}^*, \text{init} (L) = \{u \mid uv \in L for some v in \{0, 1\}^*\} ( in other words, \text{init}(L) is the set of prefixes of L) Let L = \{w \mid w \text{ is nonempty and has an equal number of $0$'s and $1$'s}\} Then \text{init}(L) is: